#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>

using namespace std;

//vector<int> ret;
//vector<int> index;
//int tmpNum[100010];
//int tmpIndex[100010];
//
//void mergesort(vector<int>& nums, int left, int right)
//{
//    if (left >= right)   return;
//
//    int mid = (left + right) >> 1;
//
//    mergesort(nums, left, mid);
//    mergesort(nums, mid + 1, right);
//
//    int cur1 = left, cur2 = mid + 1;
//    int i = 0;
//    while (cur1 <= mid && cur2 <= right)
//    {
//        if (nums[cur2] < nums[cur1])
//        {
//            ret[index[cur1]] += right - cur2 + 1;
//            tmpNum[i] = nums[cur1];
//            tmpIndex[i++] = index[cur1++];
//        }
//        else
//        {
//            tmpNum[i] = nums[cur2];
//            tmpIndex[i++] = index[cur2++];
//        }
//    }
//
//    while (cur1 <= mid)
//    {
//        tmpNum[i] = nums[cur1];
//        tmpIndex[i++] = index[cur1++];
//    }
//    while (cur2 <= right)
//    {
//        tmpNum[i] = nums[cur2];
//        tmpIndex[i++] = index[cur2++];
//    }
//
//    for (int i = left; i <= right; ++i)
//    {
//        nums[i] = tmpNum[i - left];
//        index[i] = tmpIndex[i - left];
//    }
//
//}
//
//vector<int> countSmaller(vector<int>& nums) {
//    int n = nums.size();
//
//    index.resize(n);
//    ret.resize(n);
//
//    for (int i = 0; i < n; ++i)
//    {
//        index[i] = i;
//    }
//
//    mergesort(nums, 0, n - 1);
//
//    return ret;
//}

int tmp[500010];

int mergesort(vector<int>& nums, int left, int right)
{
    if (left >= right)   return 0;

    int mid = (left + right) >> 1;

    int ret = 0;

    ret += mergesort(nums, left, mid);
    ret += mergesort(nums, mid + 1, right);

    int cur1 = left, cur2 = mid + 1;
    int i = 0;

    while (cur1 <= mid)
    {
        while (cur2 <= right && nums[cur2] >= nums[cur1] / 2.0)
        {
            cur2++;
        }
        if (cur2 > right)
        {
            break;
        }

        ret += right - cur2 + 1;
        cur1++;
    }


    cur1 = left, cur2 = mid + 1;
    i = 0;

    while (cur1 <= mid && cur2 <= right)
    {
        if (nums[cur2] < nums[cur1])
        {
            tmp[i++] = nums[cur1++];
        }
        else
        {
            tmp[i++] = nums[cur2++];
        }
    }

    while (cur1 <= mid)
    {
        tmp[i++] = nums[cur1++];
    }
    while (cur2 <= right)
    {
        tmp[i++] = nums[cur2++];
    }

    for (int i = left; i <= right; ++i)
    {
        nums[i] = tmp[i - left];
    }

    return ret;
}

int reversePairs(vector<int>& nums) {
    int n = nums.size();

    return mergesort(nums, 0, n - 1);
}

int main()
{
    vector<int> nums = { 1,3,2,3,1 };

    //countSmaller(nums);
    reversePairs(nums);
	return 0;
}
